// SPFA
// https://www.luogu.com.cn/problem/P3385

#include <cstring>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 5 + 1e3;
const int inf = 0x3f3f3f3f;

int n;
vector<pair<int, int>> adj[maxn];  // <v, w>

bool visit[maxn];
int dis[maxn], cnt[maxn];
bool SPFA(int start = 1) {
    memset(dis, inf, sizeof(dis));
    queue<int> qe;  // 待更新队列
    qe.push(start), visit[start] = 1, dis[start] = 0;
    while (!qe.empty()) {
        int u = qe.front();
        qe.pop(), visit[u] = 0;
        for (auto& p : adj[u]) {  // 遍历当前节点的邻接节点，尝试更新
            int v = p.first, w = p.second;
            if (dis[v] > dis[u] + w) {  // 更新节点路径
                dis[v] = dis[u] + w;
                if (!visit[v]) {  // v 不在队列中
                    qe.push(v), visit[v] = 1;
                    if (++cnt[v] > n) return false;  // 存在负环
                }
            }
        }
    }
    return true;
}
